package com.yeung.Divided;

import java.util.Arrays;

public class 分治求逆序数 {
    public static void main(String[] args) {
//        int[] arr = new int[]{3, 1, 2, 4};
        int arr[] = new int[]{1, 2, 3, 4, 5, 6, 7, 0};
        int count = getReverseCount(arr, 0, arr.length - 1);
        System.out.println(count);
    }

    static int getReverseCount(int[] arr, int low, int high) {
        //治
        if (low >= high) return 0;
        //分 成子问题,子问题解有三个
        //1. 左边部分的解
        //2. 右边部分的解
        //3. 左右两部分合起来的解
        int mid = (low + high) / 2;
        int lC = getReverseCount(arr, low, mid);
        int rC = getReverseCount(arr, mid + 1, high);
        int mergeC = merge(arr, low, mid, high);
        //合并子问题的解(3个)
        return lC + rC + mergeC;
    }

    private static int merge(int[] arr, int low, int mid, int high) {
        //将左右两部分的限定区间内的值拿出来(这样不会影响整体)求左右两部分合起来的解-> 把中间部分拿出来排好序在放回去
        int[] tmp = Arrays.copyOfRange(arr, low, high + 1);
        int ind = low;
        int num = 0;//逆序数
        //使用冒泡排序来记录排序多少次,就有多少个逆序
        int end = tmp.length - 1;
        //堆tmp数组进行排序
        while (true) {
            boolean changed = false;
            for (int i = 0; i < end; i++) {
                int pre = tmp[i];
                int suf = tmp[i + 1];
                if (pre > suf) {
                    int tm = pre;
                    tmp[i] = suf;
                    tmp[i + 1] = tm;

                    changed = true;
                }
            }
            if (changed) {
                end--;
                num++;
            } else {
                break;
            }
        }
        //将排好序的tmp的值,一次赋值到原始arr的low开始的局部位置
        for (int i = 0; i < tmp.length; i++) {
            arr[ind++] = tmp[i];
        }
        return num;
    }
}
